home *** CD-ROM | disk | FTP | other *** search
/ QRZ! Ham Radio 8 / QRZ Ham Radio Callsign Database - Volume 8.iso / mac / files / infodata / callbook.tar / callbook_1.3 / hash.c < prev    next >
C/C++ Source or Header  |  1991-03-31  |  5KB  |  173 lines
  1. /*
  2.  * Telnet callsign server sources copyright 1989 by Devon Bowen, KA2NRC.
  3.  * You may distribute and modify these files as you please as long as
  4.  * as long as credit to the original creator is given.
  5.  *
  6.  * This code is used to build the hash tables for the callsign server.
  7.  * Given a field number and an optional filename, it builds a two file
  8.  * hash table that allows quick reference by hash number for the field
  9.  * specified in the callsign file.
  10.  *
  11.  * The two files created by this program are callsign.X.data and
  12.  * callsign.X.search (where X is the field number the hash was done
  13.  * on). The search file is a list of constant length fields consisting
  14.  * of an unsigned int as the hash number and a file offset. Since the
  15.  * entries are constant lenghts, a binary search to find the hash
  16.  * number can be used. Once the entry is identified, the file offset
  17.  * is used to lseek into the data file. At this location in the data
  18.  * file will be a list of more file offsets terminated with a -1. The
  19.  * numbers here are offsets to all the lines in the original callsign
  20.  * file that hash to this hash number. These can then be looked at to
  21.  * see which values match the actual string.
  22.  *
  23.  * I know there are a few places this code can bomb, but since it's
  24.  * only intended to run once to build the tables, extensive error
  25.  * checking was not added. You may also have trouble with memory
  26.  * limits on your machine since this code *really* hogs memory. I
  27.  * don't really know how you might fix it if you run out of memory.
  28.  * The solution here was to generate the hash table on a machine
  29.  * that did have a sufficiently robust memory system. Then the hash
  30.  * tables were copied to the machine that was to run the server. Due
  31.  * to some endian problems some endian conversion programs had to be
  32.  * written to fix the tables as well. If you can't find a machine to
  33.  * generate the hash tables, get in touch with me and I'll see if I
  34.  * can get ours to you.
  35.  */
  36.  
  37.  
  38. #include <sys/file.h>
  39. #include <stdio.h>
  40. #include <ctype.h>
  41.  
  42. #define MAXPERHASH 10000
  43.  
  44. typedef struct link {
  45.     unsigned int offset;
  46.     struct link *next;
  47. } LINK;
  48.  
  49. char *index(), *malloc();
  50. unsigned short strhash();
  51.  
  52. LINK *last[65536], *count[65536];    /* helps stack to be global */
  53.  
  54.  
  55. main(argc, argv)
  56. int argc;
  57. char **argv;
  58. {
  59.     FILE *fd;
  60.     int fsearch, fdata;
  61.  
  62.     char *prog = argv[0];
  63.     char buf[BUFSIZ], *search;
  64.     char searchfile[BUFSIZ], datafile[BUFSIZ];
  65.  
  66.     unsigned short cur_hash=0;
  67.     int field, hash, temp;
  68.     int offsets[MAXPERHASH], bufcnt, cur_pos=0;
  69.  
  70.     if (argc != 2 && argc != 3) {
  71.         fprintf(stderr, "usage: %s field [file]\n", prog);
  72.         exit(1);
  73.     } else
  74.         field = atoi(argv[1]);
  75.  
  76.     if (argc == 3) {
  77.         fd = fopen(argv[2], "r");
  78.         if (fd == NULL) {
  79.             fprintf(stderr, "%s: %s no such file\n", prog, argv[2]);
  80.             exit(1);
  81.         }
  82.     } else
  83.         fd = stdin;
  84.  
  85.     for (temp=0; temp<=65535; temp++) {
  86.         count[temp] = (LINK *) NULL;
  87.         last[temp] = (LINK *) NULL;
  88.     }
  89.  
  90.     while (my_fgets(buf, BUFSIZ-1, fd)) {
  91.  
  92.         for (temp=0, search=buf; temp < field; temp++)
  93.             if (!(search = index(search, '|'))) {
  94.                 fprintf(stderr, "%s: bad field number\n", prog);
  95.                 exit(1);
  96.             } else
  97.                 search++;
  98.  
  99.         if (*search == '|') {
  100.             cur_pos = ftell(fd);
  101.             continue;
  102.         }
  103.  
  104.         hash = (int) strhash(search);
  105.  
  106.         if (last[hash] == (LINK *) NULL)
  107.             count[hash] = last[hash] =
  108.                     (LINK *) malloc(sizeof(LINK));
  109.         else
  110.             last[hash] = last[hash]->next =
  111.                     (LINK *) malloc(sizeof(LINK));
  112.  
  113.         if (last[hash] == (LINK *) NULL) {
  114.             fprintf(stderr, "%s: malloc failed\n", prog);
  115.             exit(1);
  116.         }
  117.  
  118.         last[hash]->next = (LINK *) NULL;
  119.         last[hash]->offset = cur_pos;
  120.  
  121.         cur_pos = ftell(fd);
  122.     }
  123.  
  124.     fclose(fd);
  125.  
  126.     sprintf(searchfile, "callsign.%d.search", field);
  127.     sprintf(datafile, "callsign.%d.data", field);
  128.  
  129.     fsearch = open(searchfile, O_WRONLY | O_CREAT, 0644);
  130.     fdata = open(datafile, O_WRONLY | O_CREAT, 0644);
  131.  
  132.     if (fsearch == -1 || fdata == -1) {
  133.         fprintf(stderr, "%s: error opening output file\n", prog);
  134.         exit(1);
  135.     }
  136.  
  137.     cur_pos = cur_hash = 0;
  138.  
  139.     do
  140.         if (count[cur_hash] != (LINK *) NULL) {
  141.  
  142.             bufcnt = 0;
  143.  
  144.             while (count[cur_hash] != (LINK *) NULL) {
  145.                 offsets[bufcnt++] = count[cur_hash]->offset;
  146.                 count[cur_hash] = count[cur_hash]->next;
  147.             }
  148.  
  149.             offsets[bufcnt++] = -1;
  150.  
  151.             if (write(fsearch,&cur_hash,sizeof(cur_hash))==-1) {
  152.                 fprintf(stderr, "%s: write failed\n", prog);
  153.                 exit(1);
  154.             }
  155.  
  156.             if (write(fsearch,&cur_pos,sizeof(cur_pos))==-1) {
  157.                 fprintf(stderr, "%s: write failed\n", prog);
  158.                 exit(1);
  159.             }
  160.  
  161.             if (write(fdata,offsets,bufcnt*sizeof(*offsets))==-1) {
  162.                 fprintf(stderr, "%s: write failed\n", prog);
  163.                 exit(1);
  164.             }
  165.  
  166.             cur_pos += bufcnt * sizeof(*offsets);
  167.         }
  168.     while (cur_hash++ != 65535);
  169.  
  170.     close(fsearch);
  171.     close(fdata);
  172. }
  173.